1. Field of the Invention
The invention relates generally to geometric modeling systems that, with the aid of a digital computer, may be used to capture, manipulate, analyze and report data. Examples of such systems include geographical positioning systems (GPS), geographic information systems (GIS), computer aided design (CAD) systems and computer aided manufacturing (CAM) systems. More particularly, the invention relates to methods which enable the subset of points, included in a given ordered set of points, that lie at a minimum distance from an arbitrarily specified point (in a given modeling coordinate system, for the modeling system supported by the digital computer), to be efficiently determined. The invention is particularly useful in situations where the given ordered set of points define a spline or polyline, and may also be applied in computer graphic systems to support graphics processing functions.
2. Definitions
The following terms and phrases are used herein and defined as follows:
1. A "polyline" is a set of at least two vertices and connecting line segment(s). PA1 2. A "modeling system" is a system that may be used to process (capture and manipulate) real world data and events, and process abstract data based on real world data and events. Examples of modeling systems include, but are not limited to, geographical positioning systems (GPS), geographic information systems (GIS), computer aided design (CAD) systems and computer aided manufacturing (CAM) systems. PA1 3. "A modeling coordinate system" is a coordinate system which maps out a space that can completely contain all of the spatial or geometric data that a user can process using a given modeling system, in terms of a user's own units (e.g., feet, miles, degrees, etc.). PA1 4. A "database coordinate system" is a coordinate system that accommodates the storage of data from a users modeling coordinate system without the loss of accuracy. PA1 5. A "device coordinate system" is a coordinate system which maps out the available space on a given device (for example, a display device), into which data may be mapped. The data may, for example, be supplied via user interaction with a display device, may be mapped from (or to) a modeling coordinate system and/or database coordinate system, etc. PA1 6. An "ordered" set of points is a set of points having a unique integer value assigned to each point in the set. PA1 7. A "spline" is a piecewise polynomial curve of degree k with up to k-1 continuous derivatives at the common joints between segments. Note, for example, that a polyline is a linear spline.
3. Description of the Prior Art
In present day modeling systems which are used, for example, for GIS, GPS, CAD and CAM applications, it is often desirable to determine from a given ordered set of points, such as an ordered set of points defining a spline or polyline (in a modeling coordinate system defined for the modeling system), which point(s) from the set is (are) closest to another arbitrarily specified point (location) in the modeling coordinate system.
Such modeling systems typically operate under the control of, or with the aid of, a digital computer. An example of one such system is the commercially available IBM 5080 computer system on which the commercially available Graphics Program Generator (GPG) software may be executed ("IBM" is a trademark owned by the International Business Machines Corporation). The GPG software is described in IBM publication number SH20-5621-04, entitled "Graphics Program Generator Program Reference", fourth edition, copyright 1990, hereby incorporated by reference to describe a present day, commercially available system in which the invention may find application.
It is known that computers that support modeling systems, computer graphics systems, etc. (such as the IBM 5080), may be used to transform a first set of signals representing a given arbitrarily specified point and a given ordered set of points (in, for example, a given modeling coordinate system), into a second set of signals identifying tile subset of points, belonging to said ordered set of points, which are located at a minimum distance from the specified point.
The known methods utilized to perform such transformations (i.e., to determine the subset of points, belonging to an ordered set of points, which are located at a minimum distance from a specified point in a given coordinate system, sometimes referred to hereinafter as "minimum distance determination methods"), can be computationally intensive. This is particularly true as the number of points being analyzed goes up, when the modeling system utilizes a 3-dimensional modeling coordinate system, and/or when the given set of points defines a spline or polyline (as compared with, for example, a simple ellipse or a circle), and can lead to an inefficient use of computing resources. In some cases, such as where many thousands or even millions points need to be analyzed, computing resources exceeding those available on a users system may be required to make the aforementioned determination.
The reason that the aforementioned problems exist using known minimum distance determination methods may be readily understood and appreciated by considering an ordered set of points which define a spline or polyline. Since the path that a spline or polyline may take is unpredictable, the only previously known way to guarantee that the proper closest point determination is made involves computing the distances exhaustively between the specified point and each (and every) point in the given ordered set of points. The distance computation for each pair of points requires summing up squares of differences and then taking the square root of the result (applying the well known Pythagorean theorem).
It should be noted that in addition to modeling systems per se, computer graphics systems also have a need to utilize minimum distance determination methods. For example, such methods are useful in processing hidden surface data.
Accordingly, it would be desirable to provide a new minimum distance determination method that can be used in geometric modeling systems and other systems (such as computer graphics systems), to guarantee the convergence to the correct solution of the aforementioned minimum distance determination problem, and at the same time reduce the amount of computation that is needed to solve such problems compared with the known minimum distance determination methods.
With respect to prior art in the field of computer graphics processing per se (as opposed to the aforementioned, more general, modeling systems which may or may not include graphics packages), those skilled in the art will readily appreciate that computer graphics systems are known in which boundary and edge areas are defined, shaded, deleted, etc., by using area clipping methods.
For example, Chang et al in, U.S. Pat. No. 5,040,130, issued Aug. 13, 1991, discloses a method for clipping a line segment boundary-defined area against a limiting plane and a related clipped extraneous edge deletion method, both for use in computer graphics display systems where graphics figures are represented by polylines of data corresponding to line segment boundary-defined areas.
Further examples of prior art computer graphics systems that utilize bounding box/clipping regions to clip polygons to lie (fit) within windows on computer output displays, to accelerate the presentation of graphic objects on such displays, to facilitate area fill processes, etc., may be found with reference to U.S. Pat. No. 5,079,719, issued Jan. 7, 1992, to Maillot; U.S. Pat. No. 5,031,114, issued Jul. 9, 1991, to Yamagami ; and U.S. Pat. No. 4,819,192, issued Apr. 4, 1989, to Kuragano et al.
In the aforementioned Yamagami patent, in order to clip a figure using a predetermined frame, coordinate values of cross points defined by a line segment representing each side of a figure to be clipped and each side of a clipping frame, or each extension line thereof, are detected. A positional relationship between the line segment and the clipping frame, and the presence or absence of cross points on the clipping frame, are obtained, respectively.
By utilizing this information, a new boundary line that did not exist in the figure before clipping can be extracted. In effect, the Yamagami patent teaches a method that determines intersections between line segments and uses this information to define boundary segments corresponding to the boundary of an object with reference to a display screen.
Although the Yamagami patent is representative of prior art that utilizes bounding box/clipping methods in graphics systems to speed up processing; nowhere, does Yamagami, or indeed any other known reference, teach, claim or even suggest using bounding box/clipping methods as part of a minimum distance determination method. As will be demonstrated hereinafter with reference to the detailed description of the invention, it would be desirable and advantageous (from the point of view of the efficient use of computing resources), to be able to provide a minimum distance determination method that utilizes bounding box/clipping techniques to determine which points, from a given ordered set of points, to discard as candidates for being closest to an arbitrarily selected point.
In the aforementioned Kuragano et al patent, tables indicating the distance between a curved surface and an observing point are formed, for use in hidden surface processing, illustrating an application for the present invention in the context of a computer graphic system. In particular, Kuragano et al teaches a system within which it is desirable to find the closest point in a given ordered set of points (on the curved surface), from an arbitrarily specified point (the observing point). However, none of the teachings in Kuragano et al are directed to the minimum distance determination methods per se.
Other background art exists which is directed to solving the problem of determining the distance between two arbitrary surfaces; as opposed to solving the problem of determining the distance between a given specified point and a given ordered set of points, in a modeling coordinate system or other coordinate system (such as a coordinate system used by a computer graphics package). Such background material is useful in understanding how distance determinations between pairs of points (on the different surfaces) are presently determined in prior art modeling and computer graphics systems.
For example, Cheng, in U.S. Pat. No. 4,989,152, issued Jan. 29, 1991, teaches a method for finding all the intersection curves of two surfaces and the absolute shortest distance "d" between the surfaces. Such methods have application in performing clearance checking for tool paths in CAD/CAM systems, etc. However, the method taught by Cheng involves constructing a plane vector field VF induced by the two given surfaces, and does not address directly solving the aforementioned minimum distance problem when only a single specified point and a given ordered set of points are given.
Still further examples of background prior art, which are directed to solving the problem of determining the distance between two arbitrary surfaces, giving insight into the present state of art and minimum distance determination techniques used in modeling and computer graphics systems (and their applications), can be found with reference to Japanese Patent JP 62-135975, issued Jun. 18, 1987; Japanese Patent JP 1-282684, issued Nov. 14, 1989; and U.S. Pat. No. 5,065,344, issued Nov. 12, 1991, to Kishimoto et al. None of these references however, or indeed any of the known prior art, is directed to providing a minimum distance determination method (as defined hereinabove), which does not require the above described exhaustive computation of distances between each point in a given ordered set of points, and an arbitrarily specified point, in a predefined coordinate system.